The need for increased portability of software programs has resulted in increased development and usage of runtime environments. The term portability refers to the ability to execute a given software program on a variety of computer platforms having different hardware, operating systems, etc. The term “runtime environment” may also be referred to as runtime system or virtual machine. The runtime environment allows software programs in source code format to be executed by a target execution platform (i.e., the hardware and operating system of a computer system) in a platform-independent manner. This means that source code instructions are not statically compiled and linked directly into native or machine code for execution by the target execution platform. Instead, the instructions are statically compiled into an intermediate language (e.g., byte-code) and the intermediate language may then be interpreted or subsequently compiled by a just-in-time (JIT) compiler within the runtime environment into native or machine code that can be executed by the target execution platform.
Object-Oriented Programming Languages (OOPLs) have been developed to improve the productivity of developing software programs. The OOPLs typically include Java (developed by Sun Microsystems, Inc.) and other programming languages conforming to CLI (Common Language Infrastructure)(developed by Microsoft Corporation). Employing OOPLs, program developers can create small, reusable sections of program code known as “objects”. The objects, once created, can be quickly and easily combined and re-used to create new programs. Some OOPLs provide open-world features (e.g., dynamic class loading, native methods, and reflection) that can dynamically link in the methods that are about to be called.
In programs written in an OOPL (e.g., Java), memory allocation and reclamation during compilation are handled entirely by the runtime environment, which relieves the programmer's burden of determining how and when to destroy unneeded objects. In this case, all objects are typically allocated to and from a common “heap” section of memory (i.e., heap allocation). The garbage collection mechanism then monitors the objects in the heap, and periodically deletes unneeded objects, thus reclaiming portions of the heap that are occupied by objects that can no longer be accessed from the user's program.
However, one problem with the heap allocation is that the users have less control over the program's performance. Each time an object is heap-allocated, a certain cost is incurred as the memory manager updates its data structures. Furthermore, an additional cost must be paid to reclaim the object during garbage collection. Although these costs are small when considered individually, the sheer frequency of object allocation and reclamation result in a significant portion of program execution time being spent in the memory manager, allocating and reclaiming memory for objects.
A prior technique has been proposed to allocate some objects on a method's stack frame (i.e., stack allocation), rather than going to the heap for each object. According to this approach, if the runtime environment can automatically detect objects whose “lifetime” does not extend beyond the method in which they are created, these objects can be automatically allocated on the stack by the JIT compiler rather than from the garbage-collected heap, resulting in improved performance. The technique used to determine which objects may be stack-allocated is called “escape analysis”. The idea of escape analysis is to determine which objects have lifetime that does not “escape” from the methods that create them. Escape analysis is a static analysis. Escape analysis makes the following analysis: an object o that does not escape from method m (i.e., whose lifetime is included in m runtime) can be stack-allocated in m.
However, problems arise when applying stack allocation for programs written in OOPLs that contain open-world features. This is due to the fact that prior escape analysis techniques rely on an inter-procedural analysis that analyzes all methods that could possibly be executed during program execution. This means that the prior escape analysis techniques are based on a statically linked code model that assumes that no new classes of objects will be loaded during runtime. In other words, the prior escape analysis techniques are based on a closed-world assumption (i.e., the program can be statically linked before execution). However and as described above, some OOPLs provide open-world features (e.g., dynamic class loading, native methods, and reflection). These open-world features will render the closed-world assumption unrealistic, which will be explained below.
For example, dynamic class loading allows dynamic linking of methods or functions that are about to be called within a runtime context. However, loading a class dynamically into a runtime environment that is executing a previously optimized program (e.g., a program from which synchronization has been removed in whole or in part) may cause the program to behave in an unsafe manner (e.g., data contention) or fail. While the prior escape analysis techniques based on a statically linked code model can be used to remove synchronization from statically linked code, these techniques do not support the restoration of synchronization to previously desynchronized (i.e., optimized) code that subsequently requires synchronization due to the effects of a dynamically loaded class. Additionally, other open-world features such as reflection and native methods can invalidate an escape analysis, thereby leading to unsafe execution conditions.
Thus, there exists a need for providing stack allocation to programs that have open world features.